{
  // 5. 最长回文子串

  // 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

  // 示例 1：
  // 输入: "babad"
  // 输出: "bab"
  // 注意: "aba" 也是一个有效答案。

  // 示例 2：
  // 输入: "cbbd"
  // 输出: "bb"

  /* 
    @param {string} s
    @return {string}
  */
  let longestPalindrome = function (s) {
    // 思路中心扩展法
    let result = s[0] || '';
    for (let i = 1; i < s.length; i++) {
      for (let j = i; j <= 2; j++) {
        // 奇偶会文串
        let left = i;
        let right = i + j;
        if (left >= 0 && right < s.length && s[left] === s[right]) {
          // 向外（即两端）扩展直至不同
          left--;
          right++;
        }
        let length = right - left - 1; //  (right - 1) - (left + 1) - 1
        if (length > result.length) {
          result = s.substr(left + 1, length);
        }
      }
    }
    return result;

    // let len = s.length;
    // function getMax(left, right) {
    //   while (left >= 0 && right < len && s[left] === s[right]) {
    //     left--
    //     right++
    //   }
    //   return {
    //     left: left + 1, // 因为while循环停止时left已经--，所以应该退一格，right同理
    //     right: right - 1
    //   }
    // }
    // let start = 0, end = 0
    // for (let i = 0; i < len; i++) {
    //   let obj = getMax(i, i) // aba 型
    //   let obj1 = getMax(i, i + 1) // abba 型
    //   let f = obj.right - obj.left > obj1.left - obj1.right;

    //   let maxObj = f ? obj : obj1;
    //   if (maxObj.right - maxObj.left > end - start) {
    //     start = maxObj.left
    //     end = maxObj.right
    //   }
    // }
    // return s.substr(start, end + 1);

    // 动态规划
    // 解题思路
    // 了解dp[j][i]代表从j->i
    // dp[j+1][i-1]代表的是子字符串的首->尾
    // 然后就是动态创建二维数组的过程

    // 测试用例："babad"
    // 我们把这个二维数组进行转换再看看
    // [
    //   // [0,0], [0,1], [0,2]……
    //   ↓      ↓     ↓
    //   [true, false, true, false, false],
    //   [0, true, false, true, false],
    //   [0, 0, true, false, false],
    //   [0, 0, 0, true, false],
    //   [0, 0, 0, 0, true]
    // ]
    let len = s.length;
    let res = '';
    // 创建二维数组
    let dp = Array.from(new Array(len), () => new Array(len).fill(0));
    // 从字符串首部开始
    for (let i = 0; i < len; i++) {
      // 从字符串i前开始依次向前查找
      for (let j = i; j >= 0; j--) {
        dp[j][i] = s[i] === s[j] && (i - j < 2 || dp[j + 1][i - 1]);
        if (dp[j][i] && i - j + 1 > res.length) {
          res = s.substr(j, i + 1);
        }
      }
    }
    return res;
  };
}

{
  // 134. 加油站
  // 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
  // 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
  // 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

  // 说明:
  // 如果题目有解，该答案即为唯一答案。
  // 输入数组均为非空数组，且长度相同。
  // 输入数组中的元素均为非负数。

  // 示例 1:
  // 输入:
  // gas  = [1,2,3,4,5]
  // cost = [3,4,5,1,2]
  // 输出: 3
  // 解释:
  // 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
  // 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
  // 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
  // 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
  // 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
  // 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
  // 因此，3 可为起始索引。

  // 示例 2:
  // 输入:
  // gas  = [2,3,4]
  // cost = [3,4,3]
  // 输出: -1
  // 解释:
  // 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
  // 我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
  // 开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
  // 开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
  // 你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
  // 因此，无论怎样，你都不可能绕环路行驶一周。

  /**
   * @param {number[]} gas
   * @param {number[]} cost
   * @returns {number}
   */
  let canCompleteCircuit = function (gas, cost) {
    // 法一 思路
    // 1 计算总剩余量
    // 2 找出总剩余量最低点
    // const len = gas.length;
    // let innage = 0; // 剩余总量
    // let minInnage = Number.MAX_VALUE; // 剩余油量最低点
    // let res = 0;
    // for (let i = 0; i < len; i++) {
    //   innage += gas[i] - cost[i];
    //   if (innage < minInnage) {
    //     minInnage = innage;
    //     res = (i + 1) % len; // 最低点的下一个点 就是最适合出的出发点
    //   }
    // }
    // return innage < 0 ? -1 : res;

    const len = gas.length;

    // diff数组，diff[i]为gas[i]-cost[i]，表示从第i个加油站到第i+1个加油站油量的变化
    let diff = Array.from({ length: len }, (v, i) => gas[i] - cost[i]);

    // 如果diff数组的和小于0，表示加油站里的油量不够车跑一圈
    if (diff.reduce((a, b) => a + b) < 0) {
      return -1;
    }

    let temp = 0; // 当前油量
    let res = 0; // 当前加油站编号
    for (let i = 0; i < len; i++) {
      // 计算当前油量
      temp += diff[i];
      // 如果当前油量小于0，表邮箱在到达下一个加油站之前就空了，也就是跑不到下一个加油站
      if (temp < 0) {
        // 则将在一个加油站当作为起点，将当前油量制清0
        temp = 0;
        res = i + 1;
      }
    }
    return res;
  };
  console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]));
  console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3]));
}

{
  // 最长递增子序列 or 最长上升子序列
  // 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度
  // 示例 1：
  // 输入：nums = [10,9,2,5,3,7,101,18]
  // 输出：4
  // 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
  //
  // 示例 2：
  // 输入：nums = [0,1,0,3,2,3]
  //
  // 输出：4
  //
  // 示例 3：
  // 输入：nums = [7,7,7,7,7,7,7]
  // 输出：1

  /**
   * @param {number[]} nums
   * @return {number}
   */

  // 法一 动态规划
  var lengthOfLIS = function (nums) {
    let len = nums.length;
    if (len === 0) return 0;

    // 初始化为1，因为子序列最少包含自己，即1
    // let dp = new Array(len).fill(1);
    let dp = Array.from({ length: len }, () => 1);

    // dp数组的最大值
    let max = 0;
    for (let i = 0; i < len; i++) {
      for (let j = 0; j < i; j++) {
        // 因为求的是递增子序列，所以前面的数nums[j]必须小于nums[i]才算递增子序列，才可以计算最大值
        // 加1为在nums[j]的最长递增子序列dp[j]基础上加上当前元素nums[i]所得的最长递增子序列
        if (nums[j] < nums[i]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      max = Math.max(max, dp[i]);
    }

    return max;
  };

  console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));
}

{
  // 合并二维有序数组成一维有序数组，归并排序的思路
  function mergeSort(arr) {
    const len = arr.length;
    if (len <= 1) {
      return arr[0];
    }
    // 计划分割点
    let mid = Math.floor(len / 2);
    // 递归处理左子数组，然后合并为有序数组
    let leftArr = mergeSort(arr.slice(0, mid));
    // 递归处理右子数组，然后合并为有序数组
    let rightArr = mergeSort(arr.slice(mid, len));
    // 合并左右两个数组
    arr = mergeArr(leftArr, rightArr);
    // 返回合并后的数组
    return arr;
  }

  function mergeArr(arr1, arr2) {
    // 初始化两个指针 分别指向arr1和arr2
    let i = 0;
    let j = 0;
    const res = [];
    let len1 = arr1.length;
    let len2 = arr2.length;

    // 合并两个子数组
    while (i < len1 && j < len2) {
      if (arr1[i] < arr2[j]) {
        res.push(arr1[i]);
        i++;
      } else {
        res.push(arr2[j]);
        j++;
      }
    }

    // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
    if (i < len1) {
      return res.concat(arr1.slice(i));
    } else {
      return res.concat(arr2.slice(j));
    }
  }

  var arr = [
    [1, 2, 4],
    [2, 3, 7],
    [3, 5, 7],
    [4, 5, 8],
  ];
  console.log(mergeSort(arr));
}
